def kmp_matcher(T, P):
    n = len(T)
    m = len(P)
    pi = compute_prefix(P)
    q = 0
    for i in xrange(n):
        while q > 0 and P[q] != T[i]:
            q = pi[q]
        if P[q] == T[i]:
            q += 1
        if q == m:
            print 'Pattern occurs with shift', i - m + 1
            q = pi[m - 1]

def compute_prefix(P):
    m = len(P)
    pi = [0] * m
    k = 0
    for q in xrange(1, m):
        while k > 0 and P[k] != P[q]:
            k = pi[k]
        if P[k] == P[q]:
            k += 1
        pi[q] = k
    return pi

if __name__ == '__main__':
    T = 'abababcaabababcaaaabababca'
    P = 'abababca'
    print 'T:', T
    print 'P:', P
    kmp_matcher(T, P)
